|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Immutable;
using Microsoft.CodeAnalysis.Collections.Internal;
namespace Microsoft.CodeAnalysis.Collections
{
/// <summary>
/// Represents a segmented hash set that is immutable; meaning it cannot be changed once it is created.
/// </summary>
/// <remarks>
/// <para>There are different scenarios best for <see cref="ImmutableSegmentedHashSet{T}"/> and others
/// best for <see cref="ImmutableHashSet{T}"/>.</para>
///
/// <para>The following table summarizes the performance characteristics of
/// <see cref="ImmutableSegmentedHashSet{T}"/>:</para>
///
/// <list type="table">
/// <item>
/// <description>Operation</description>
/// <description><see cref="ImmutableSegmentedHashSet{T}"/> Complexity</description>
/// <description><see cref="ImmutableHashSet{T}"/> Complexity</description>
/// <description>Comments</description>
/// </item>
/// <item>
/// <description>Contains</description>
/// <description>O(1)</description>
/// <description>O(log n)</description>
/// <description>Directly index into the underlying segmented list</description>
/// </item>
/// <item>
/// <description>Add()</description>
/// <description>O(n)</description>
/// <description>O(log n)</description>
/// <description>Requires creating a new segmented hash set and cloning all impacted segments</description>
/// </item>
/// </list>
///
/// <para>This type is backed by segmented arrays to avoid using the Large Object Heap without impacting algorithmic
/// complexity.</para>
/// </remarks>
/// <typeparam name="T">The type of the value in the set.</typeparam>
/// <devremarks>
/// <para>This type has a documented contract of being exactly one reference-type field in size. Our own
/// <see cref="RoslynImmutableInterlocked"/> class depends on it, as well as others externally.</para>
///
/// <para><strong>IMPORTANT NOTICE FOR MAINTAINERS AND REVIEWERS:</strong></para>
///
/// <para>This type should be thread-safe. As a struct, it cannot protect its own fields from being changed from one
/// thread while its members are executing on other threads because structs can change <em>in place</em> simply by
/// reassigning the field containing this struct. Therefore it is extremely important that <strong>⚠⚠ Every member
/// should only dereference <c>this</c> ONCE ⚠⚠</strong>. If a member needs to reference the
/// <see cref="_set"/> field, that counts as a dereference of <c>this</c>. Calling other instance members
/// (properties or methods) also counts as dereferencing <c>this</c>. Any member that needs to use <c>this</c> more
/// than once must instead assign <c>this</c> to a local variable and use that for the rest of the code instead.
/// This effectively copies the one field in the struct to a local variable so that it is insulated from other
/// threads.</para>
/// </devremarks>
internal readonly partial struct ImmutableSegmentedHashSet<T> : IImmutableSet<T>, ISet<T>, ICollection, IEquatable<ImmutableSegmentedHashSet<T>>
{
/// <inheritdoc cref="ImmutableHashSet{T}.Empty"/>
public static readonly ImmutableSegmentedHashSet<T> Empty = new(new SegmentedHashSet<T>());
private readonly SegmentedHashSet<T> _set;
private ImmutableSegmentedHashSet(SegmentedHashSet<T> set)
{
_set = set;
}
/// <inheritdoc cref="ImmutableHashSet{T}.KeyComparer"/>
public IEqualityComparer<T> KeyComparer => _set.Comparer;
/// <inheritdoc cref="ImmutableHashSet{T}.Count"/>
public int Count => _set.Count;
public bool IsDefault => _set == null;
/// <inheritdoc cref="ImmutableHashSet{T}.IsEmpty"/>
public bool IsEmpty => _set.Count == 0;
bool ICollection<T>.IsReadOnly => true;
bool ICollection.IsSynchronized => true;
object ICollection.SyncRoot => _set;
public static bool operator ==(ImmutableSegmentedHashSet<T> left, ImmutableSegmentedHashSet<T> right)
=> left.Equals(right);
public static bool operator !=(ImmutableSegmentedHashSet<T> left, ImmutableSegmentedHashSet<T> right)
=> !left.Equals(right);
public static bool operator ==(ImmutableSegmentedHashSet<T>? left, ImmutableSegmentedHashSet<T>? right)
=> left.GetValueOrDefault().Equals(right.GetValueOrDefault());
public static bool operator !=(ImmutableSegmentedHashSet<T>? left, ImmutableSegmentedHashSet<T>? right)
=> !left.GetValueOrDefault().Equals(right.GetValueOrDefault());
/// <inheritdoc cref="ImmutableHashSet{T}.Add(T)"/>
public ImmutableSegmentedHashSet<T> Add(T value)
{
var self = this;
if (self.IsEmpty)
{
var set = new SegmentedHashSet<T>(self.KeyComparer) { value };
return new ImmutableSegmentedHashSet<T>(set);
}
else if (self.Contains(value))
{
return self;
}
else
{
// TODO: Reuse all pages with no changes
var builder = self.ToValueBuilder();
builder.Add(value);
return builder.ToImmutable();
}
}
/// <inheritdoc cref="ImmutableHashSet{T}.Clear()"/>
public ImmutableSegmentedHashSet<T> Clear()
{
var self = this;
if (self.IsEmpty)
{
return self;
}
return Empty.WithComparer(self.KeyComparer);
}
/// <inheritdoc cref="ImmutableHashSet{T}.Contains(T)"/>
public bool Contains(T value)
=> _set.Contains(value);
/// <inheritdoc cref="ImmutableHashSet{T}.Except(IEnumerable{T})"/>
public ImmutableSegmentedHashSet<T> Except(IEnumerable<T> other)
{
var self = this;
if (other is ImmutableSegmentedHashSet<T> { IsEmpty: true })
{
return self;
}
else if (self.IsEmpty)
{
// Enumerate the argument to match behavior of ImmutableHashSet<T>
foreach (var _ in other)
{
// Intentionally empty
}
return self;
}
else
{
// TODO: Reuse all pages with no changes
var builder = self.ToValueBuilder();
builder.ExceptWith(other);
return builder.ToImmutable();
}
}
/// <inheritdoc cref="ImmutableHashSet{T}.GetEnumerator()"/>
public Enumerator GetEnumerator()
=> new(_set);
/// <inheritdoc cref="ImmutableHashSet{T}.Intersect(IEnumerable{T})"/>
public ImmutableSegmentedHashSet<T> Intersect(IEnumerable<T> other)
{
var self = this;
if (self.IsEmpty || other is ImmutableSegmentedHashSet<T> { IsEmpty: true })
{
return self.Clear();
}
else
{
// TODO: Reuse all pages with no changes
var builder = self.ToValueBuilder();
builder.IntersectWith(other);
return builder.ToImmutable();
}
}
/// <inheritdoc cref="ImmutableHashSet{T}.IsProperSubsetOf(IEnumerable{T})"/>
public bool IsProperSubsetOf(IEnumerable<T> other)
=> _set.IsProperSubsetOf(other);
/// <inheritdoc cref="ImmutableHashSet{T}.IsProperSupersetOf(IEnumerable{T})"/>
public bool IsProperSupersetOf(IEnumerable<T> other)
=> _set.IsProperSupersetOf(other);
/// <inheritdoc cref="ImmutableHashSet{T}.IsSubsetOf(IEnumerable{T})"/>
public bool IsSubsetOf(IEnumerable<T> other)
=> _set.IsSubsetOf(other);
/// <inheritdoc cref="ImmutableHashSet{T}.IsSupersetOf(IEnumerable{T})"/>
public bool IsSupersetOf(IEnumerable<T> other)
=> _set.IsSupersetOf(other);
/// <inheritdoc cref="ImmutableHashSet{T}.Overlaps(IEnumerable{T})"/>
public bool Overlaps(IEnumerable<T> other)
=> _set.Overlaps(other);
/// <inheritdoc cref="ImmutableHashSet{T}.Remove(T)"/>
public ImmutableSegmentedHashSet<T> Remove(T value)
{
var self = this;
if (!self.Contains(value))
{
return self;
}
else
{
// TODO: Reuse all pages with no changes
var builder = self.ToValueBuilder();
builder.Remove(value);
return builder.ToImmutable();
}
}
/// <inheritdoc cref="ImmutableHashSet{T}.SetEquals(IEnumerable{T})"/>
public bool SetEquals(IEnumerable<T> other)
=> _set.SetEquals(other);
/// <inheritdoc cref="ImmutableHashSet{T}.SymmetricExcept(IEnumerable{T})"/>
public ImmutableSegmentedHashSet<T> SymmetricExcept(IEnumerable<T> other)
{
var self = this;
if (other is ImmutableSegmentedHashSet<T> otherSet)
{
if (otherSet.IsEmpty)
return self;
else if (self.IsEmpty)
return otherSet.WithComparer(self.KeyComparer);
}
if (self.IsEmpty)
{
return ImmutableSegmentedHashSet.CreateRange(self.KeyComparer, other);
}
else
{
// TODO: Reuse all pages with no changes
var builder = self.ToValueBuilder();
builder.SymmetricExceptWith(other);
return builder.ToImmutable();
}
}
/// <inheritdoc cref="ImmutableHashSet{T}.TryGetValue(T, out T)"/>
public bool TryGetValue(T equalValue, out T actualValue)
{
if (_set.TryGetValue(equalValue, out var value))
{
actualValue = value;
return true;
}
actualValue = equalValue;
return false;
}
/// <inheritdoc cref="ImmutableHashSet{T}.Union(IEnumerable{T})"/>
public ImmutableSegmentedHashSet<T> Union(IEnumerable<T> other)
{
var self = this;
if (other is ImmutableSegmentedHashSet<T> otherSet)
{
if (otherSet.IsEmpty)
return self;
else if (self.IsEmpty)
return otherSet.WithComparer(self.KeyComparer);
}
// TODO: Reuse all pages with no changes
var builder = self.ToValueBuilder();
builder.UnionWith(other);
return builder.ToImmutable();
}
/// <inheritdoc cref="ImmutableHashSet{T}.ToBuilder()"/>
public Builder ToBuilder()
=> new(this);
private ValueBuilder ToValueBuilder()
=> new ValueBuilder(this);
/// <inheritdoc cref="ImmutableHashSet{T}.WithComparer(IEqualityComparer{T}?)"/>
public ImmutableSegmentedHashSet<T> WithComparer(IEqualityComparer<T>? equalityComparer)
{
var self = this;
equalityComparer ??= EqualityComparer<T>.Default;
if (Equals(self.KeyComparer, equalityComparer))
return self;
return new ImmutableSegmentedHashSet<T>(new SegmentedHashSet<T>(self._set, equalityComparer));
}
public override int GetHashCode()
=> _set?.GetHashCode() ?? 0;
public override bool Equals(object? obj)
=> obj is ImmutableSegmentedHashSet<T> other && Equals(other);
public bool Equals(ImmutableSegmentedHashSet<T> other)
=> _set == other._set;
IImmutableSet<T> IImmutableSet<T>.Clear()
=> Clear();
IImmutableSet<T> IImmutableSet<T>.Add(T value)
=> Add(value);
IImmutableSet<T> IImmutableSet<T>.Remove(T value)
=> Remove(value);
IImmutableSet<T> IImmutableSet<T>.Intersect(IEnumerable<T> other)
=> Intersect(other);
IImmutableSet<T> IImmutableSet<T>.Except(IEnumerable<T> other)
=> Except(other);
IImmutableSet<T> IImmutableSet<T>.SymmetricExcept(IEnumerable<T> other)
=> SymmetricExcept(other);
IImmutableSet<T> IImmutableSet<T>.Union(IEnumerable<T> other)
=> Union(other);
void ICollection<T>.CopyTo(T[] array, int arrayIndex)
=> _set.CopyTo(array, arrayIndex);
void ICollection.CopyTo(Array array, int index)
{
if (array is null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
if (index < 0)
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
if (array.Length < index + Count)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index);
foreach (var item in this)
{
array.SetValue(item, index++);
}
}
IEnumerator<T> IEnumerable<T>.GetEnumerator()
=> GetEnumerator();
IEnumerator IEnumerable.GetEnumerator()
=> GetEnumerator();
bool ISet<T>.Add(T item)
=> throw new NotSupportedException();
void ISet<T>.UnionWith(IEnumerable<T> other)
=> throw new NotSupportedException();
void ISet<T>.IntersectWith(IEnumerable<T> other)
=> throw new NotSupportedException();
void ISet<T>.ExceptWith(IEnumerable<T> other)
=> throw new NotSupportedException();
void ISet<T>.SymmetricExceptWith(IEnumerable<T> other)
=> throw new NotSupportedException();
void ICollection<T>.Add(T item)
=> throw new NotSupportedException();
void ICollection<T>.Clear()
=> throw new NotSupportedException();
bool ICollection<T>.Remove(T item)
=> throw new NotSupportedException();
}
}
|